# 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
# 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
# ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
# [[],[1],[2],[],[3],[]]
# 输出：[null,null,null,1.50000,null,2.00000]
import heapq


class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.big_heap = []
        self.small_heap = []

    def addNum(self, num: int) -> None:
        if not self.big_heap or self.big_heap[0] < -num:
            heapq.heappush(self.big_heap, -num)
            if len(self.big_heap) > len(self.small_heap) + 1:
                heapq.heappush(self.small_heap, -heapq.heappop(self.big_heap))
        else:
            heapq.heappush(self.small_heap, num)
            if len(self.small_heap) > len(self.big_heap) + 1:
                heapq.heappush(self.big_heap, -heapq.heappop(self.small_heap))


    def findMedian(self) -> float:
        if len(self.big_heap) > len(self.small_heap):
            return -self.big_heap[0]
        elif len(self.big_heap) < len(self.small_heap):
            return self.small_heap[0]
        else:
            return (self.small_heap[0] - self.big_heap[0])/2
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
